# https://leetcode.com/problems/4sum-ii
import collections
class Solution:
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        A, B, C, D = collections.Counter(A), collections.Counter(B), collections.Counter(C), collections.Counter(D)
        output = 0
        for a in A:
            for b in B:
                for c in C:
                    if -a - b - c in D:
                        output += (A[a] * B[b] * C[c] * D[-a - b - c])
        return output


class Solution:
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """
        AB=collections.Counter(a+b for a in A for b in B)
        return sum(AB[-c-d] for c in C for d in D)

A = [1, 2]
B = [-2, -1]
C = [-1, 2]
D = [0, 2]


A=[-268435121,-268434818,-268435384,-268434504,-268434852,-268434847,-268434718,-268434830,-268434644,-268434843,-268435282,-268434756,-268435098,-268435361,-268434888,-268435198,-268434771,-268435001,-268435011,-268434745,-268434892,-268435442,-268434705,-268434932,-268435095,-268434829,-268435166,-268434672,-268434959,-268434886,-268435158,-268435439,-268434665,-268434561,-268435327,-268434478,-268434879,-268434902,-268435027,-268434922,-268435028,-268434950,-268435407,-268434916,-268435326,-268435048,-268435156,-268435043,-268434607,-268434738,-268434944,-268434813,-268435194,-268434793,-268435372,-268434483,-268434761,-268434571,-268434529,-268435314,-268434733,-268435218,-268434590,-268434520,-268435372,-268435180,-268435420,-268435360,-268435316,-268435455,-268434797,-268435008,-268434540,-268434816,-268434485,-268435238,-268434559,-268434589,-268435257,-268434877,-268435455,-268435128,-268435307,-268434919,-268434893,-268435239,-268434788,-268435176,-268434930,-268434582,-268434471,-268435206,-268434561,-268434880,-268435137,-268434504,-268434549,-268434825,-268434587,-268435293]
B=[-268434497,-268435316,-268435433,-268434992,-268435391,-268434629,-268434902,-268434629,-268434895,-268434527,-268434822,-268435325,-268434634,-268434877,-268434758,-268434758,-268435109,-268435179,-268434736,-268435111,-268435243,-268435191,-268435091,-268435041,-268435231,-268434473,-268434656,-268435379,-268435127,-268434727,-268435302,-268434643,-268435101,-268434879,-268434848,-268434880,-268434817,-268434746,-268435005,-268435018,-268434535,-268435390,-268435430,-268434486,-268434497,-268434652,-268434816,-268435055,-268435296,-268435044,-268434939,-268435267,-268435283,-268434673,-268435298,-268435069,-268435041,-268434525,-268435023,-268435064,-268434969,-268434630,-268435197,-268435049,-268434496,-268434777,-268434928,-268434683,-268434923,-268434699,-268434634,-268434613,-268435438,-268435449,-268434498,-268435183,-268434577,-268434515,-268435100,-268435023,-268435214,-268435358,-268435394,-268434734,-268434636,-268435056,-268434829,-268434962,-268434673,-268434578,-268434850,-268435294,-268434752,-268435410,-268434841,-268434952,-268435111,-268434905,-268434791,-268434507]
C=[268434624,268434831,268435028,268434547,268435027,268435453,268435101,268435378,268435107,268434991,268435147,268435379,268435435,268435439,268435003,268435440,268435454,268434786,268434521,268434678,268435125,268434685,268434482,268435042,268434486,268434521,268435003,268435086,268434786,268434762,268435384,268434577,268435199,268435020,268434709,268435006,268434820,268434830,268435208,268435448,268435274,268435438,268435082,268435140,268434465,268435324,268434645,268435032,268434567,268435057,268435161,268435246,268434515,268434880,268435432,268434905,268435135,268435436,268434923,268435110,268434607,268435286,268435281,268434717,268435367,268434894,268435280,268434880,268435181,268434971,268435316,268435021,268435208,268434589,268434811,268434774,268434843,268434762,268434650,268435068,268434731,268435192,268434596,268434549,268434535,268435372,268435361,268435224,268435033,268434807,268435003,268434647,268435051,268434464,268435326,268434991,268434571,268435192,268435435,268435181]
D=[268434917,268435022,268435311,268434898,268435389,268435347,268434735,268435285,268434695,268434794,268435393,268435114,268435063,268434517,268434464,268434766,268435316,268434706,268434962,268435078,268434921,268435070,268434569,268434895,268435446,268435003,268435362,268435421,268435158,268435274,268435391,268435298,268435311,268435295,268435428,268435010,268434884,268435055,268434824,268434877,268434467,268435181,268434797,268435142,268434611,268434719,268435081,268434924,268435340,268434961,268435215,268434583,268435192,268435364,268434925,268435396,268434599,268435330,268435253,268435037,268434642,268435228,268435103,268434736,268435123,268435220,268435394,268435015,268434906,268434478,268434956,268434465,268434840,268434648,268434706,268435382,268435297,268434602,268435264,268435237,268434582,268434686,268434825,268435246,268435234,268435441,268435139,268435357,268434512,268435375,268434873,268435318,268434469,268434750,268435217,268434469,268434872,268435218,268435254,268434547]
Solution().fourSumCount(A, B, C, D)

